//104 Maximum Depth of Binary Tree
/*
求一个二叉树的最大深度

*/

//
int maxDepth(TreeNode *root)
{
	return root ? 1 + max(maxDepth(root->left), maxDepth(root->right)) : 0;
}

//深度优先搜索
class Solution
{
public:
	int maxDepth(TreeNode *root)
	{
		if (root == nullptr)
			return 0;

		//返回左结点和右结点中最大
		return max(maxDepth(root->left), maxDepth(root->right)) + 1;
	}
};

//广度优先搜索
class Solution
{
public:
	int maxDepth(TreeNode *root)
	{
		if (root == nullptr)
			return 0;
		queue<TreeNode *> Q;
		Q.push(root);
		int ans = 0;

		//
		while (!Q.empty())
		{
			int sz = Q.size();

			//还有结点就会不断计算，直到最后null
			while (sz > 0)
			{
				TreeNode *node = Q.front();
				Q.pop();
				if (node->left)
					Q.push(node->left);
				if (node->right)
					Q.push(node->right);
				sz -= 1;
			}
			ans += 1;
		}
		return ans;
	}
};
